/*
 * @lc app=leetcode.cn id=239 lang=cpp
 *
 * [239] 滑动窗口最大值
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 即使用了记忆最大值还是会超时，似乎必须在插入dq时就按顺序排
        // 但这样我又不知道现在希望插入的和弹出的那个数被排到哪去了

        // 结果答案里的dq存的是数的index，直接去nums里拿索引找就完了
        // 我&%￥*#%@#
        // wtm

        // 没有必要一定插入时放在front顶部。。。
        deque<int> dq;
        vector<int> ans;
        for (int i = 0; i < nums.size(); ++i) {
            // 这个是
            // 最大数就是左端弹出数，把这个从front弹出
            if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
            }
            // 新数nums[i]比较大，从back往front删除比新数小的
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }
            // 然后新数放back，如果新数就是最大的会在上一步把所有数
            // 删了然后插完新数dq只有1个数

            // 因为是放在back，有一样的最大值时也是在后面，
            // 会先判断之前插入的最大值到达窗口左侧弹出
            dq.push_back(i);
            if (i >= k - 1) {
                ans.push_back(nums[dq.front()]);
            }
        }
        return ans;
    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 优先队列还能自动对pair排列的么。。。
        int n = nums.size();
        std::priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }

    // vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    //     // 其实也是可以用map的，但问题是用emplace新插入的数字之前存在
    //     // 好像默认什么也不做
    //     // 即使multimap也没用

    //     // 所以需要在插入前去除窗口外的，再emplace默认插入

    //     // 算了什么鬼。。。
        
    //     std::vector<int> res;
    //     // <num, index>
    //     std::multimap<int, int, std::greater<int>> slideWindow;
    //     for (int i=0;i<k;i++){
    //         slideWindow.emplace(nums[i], i);
    //     }
    //     res.emplace_back((slideWindow.begin())->first);
    //     for (int j=k;j<nums.size();++j){
    //         for (auto iter=slideWindow.begin();iter!=slideWindow.end();iter++){
    //             if (iter->second <= j-k){
    //                 iter = slideWindow.erase(iter);
    //             }
    //         }
    //         slideWindow.emplace(nums[j], j);
            
    //         //  or iter != slideWindow.begin()
    //         res.emplace_back((slideWindow.begin())->first);
    //     }
    //     return res;
    // }

    // vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    //     // 记一下吧，直接双端不管大小绝逼超时
    //     // 然后想怎么记住最大值

    //     // 实际上最简单的就是在塞进去拿出来的时候排序
    //     deque<int> dq;
    //     for (int i=0;i<k;++i){
    //         dq.push_back(nums[i]);
    //     }
    //     vector<int> result;
    //     int max = *(max_element(dq.begin(), dq.end()));
    //     result.emplace_back(max);
    //     int maxNum = 0;
    //     for (int i=0;i<k;++i){
    //         if (nums[i] == max){++maxNum;}
    //     }

    //     for (int j=0;j<nums.size()-k;++j){
    //         dq.pop_front();
    //         dq.push_back(nums[j+k]);
    //         if (nums[j+k] > max){
    //             max = nums[j+k];
    //             maxNum = 1;
    //         } else if (nums[j+k] == max){
    //             maxNum++;
    //         }

    //         if (nums[j] == max){
    //             maxNum--;
    //         }

    //         if (maxNum == 0){
    //             max = *(max_element(dq.begin(), dq.end()));
    //             for (int i=0;i<k;++i){
    //                 if (nums[j+1+i] == max){maxNum++;}
    //             }
    //         }
    //         result.emplace_back(max);
    //     }
    //     return result;
    // }
};
// @lc code=end

